#include <iostream> 
#include <cstdio>
using namespace std;
#define N 110
string src[N];
string ans[N][2];
int main()
{
	int m,n;
	cin>>m>>n;
	getchar();
	for(int i=0;i<m;i++){
		getline(cin,src[i]);
	}
	for(int i=0;i<n;i++){
		getline(cin,ans[i][1]);
		int p=ans[i][1].find_first_of(" ");
		string order(ans[i][1],0,p);
		order="{{ "+order+" }}";
		ans[i][0]=order;
		ans[i][1].erase(0,p+2);
		int rear=ans[i][1].length()-1;
		ans[i][1].erase(rear,1);
		for(int j=0;j<m;j++){
			int pos=src[j].find(ans[i][0]);
			while(pos!=string::npos){
				src[j].erase(pos,ans[i][0].length());
				src[j].insert(pos,ans[i][1]);
				pos+=ans[i][0].length();
				pos=src[j].find(ans[i][0],pos);
			}
		}
		
	}
	for(int i=0;i<m;i++){
		cout<<src[i]<<endl;
	}
	return 0;
}
